QUBO & Ising Models
David E. Bernal NeiraDavidson School of Chemical Engineering, Purdue University
Pedro Maciel Xavier
Davidson School of Chemical Engineering, Purdue University
Computer Science & Systems Engineering Program, Federal University of Rio de Janeiro
Benjamin J. L. Murray
Davidson School of Chemical Engineering, Purdue University
Undergraduate Research Assistant
Quadratic Unconstrained Binary Optimization#
This notebook will explain the basics of the QUBO modeling. In order to implement the different QUBOs we will use D-Wave’s packages dimod, and then solve them using neal’s implementation of simulated annealing. We will also leverage the use of D-Wave’s package dwavebinarycsp to translate constraint satisfaction problems to QUBOs. Finally, for Groebner basis computations we will use Sympy for symbolic computation in Python and Networkx for network models/graphs.
Problem statement#
We define a QUBO as the following optimization problem:
\[
\min_{x \in \{0,1 \}^n} \sum_{(ij) \in E(G)} Q_{ij}x_i x_j + \sum_{i \in V(G)}Q_{ii}x_i + c_Q = \min_{x \in \{0,1 \}^n} x^\top Q x + c_Q
\]
where we optimize over binary variables \(x \in \{ 0,1 \}^n\), on a constrained graph \(G(V,E)\) defined by an adjacency matrix \(Q\). We also include an arbitrary offset \(c_Q\).
Example#
Suppose we want to solve the following problem via QUBO $\( \min_{\mathbf{x}} 2𝑥_0+4𝑥_1+4𝑥_2+4𝑥_3+4𝑥_4+4𝑥_5+5𝑥_6+4𝑥_7+5𝑥_8+6𝑥_9+5𝑥_{10} \\ s.t. \begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \end{bmatrix}\mathbf{x}= \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix} \\ \mathbf{x} \in \{0,1 \}^{11} \)$
# If using this on Google collab, we need to install the packages
try:
import google.colab
IN_COLAB = True
except:
IN_COLAB = False
# Let's install dimod, neal, and pyomo
if IN_COLAB:
!pip install -q pyomo
!pip install dimod
!pip install dwave-neal
# Import the Pyomo library, which can be installed via pip, conda or from Github https://github.com/Pyomo/pyomo
import pyomo.environ as pyo
# Import the Dwave packages dimod and neal
import dimod
import neal
# Import Matplotlib to generate plots
import matplotlib.pyplot as plt
# Import numpy and scipy for certain numerical calculations below
import numpy as np
from scipy.special import gamma
import math
from collections import Counter
import pandas as pd
from itertools import chain
import time
import networkx as nx
First we would write this problem as an unconstrained one by penalizing the linear constraints as quadratics in the objective. Let’s first define the problem parameters
A = np.array([[1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1],
[0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1],
[0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1]])
b = np.array([1, 1, 1])
c = np.array([2, 4, 4, 4, 4, 4, 5, 4, 5,6, 5])
In order to define the \(\mathbf{Q}\) matrix, we first write the problem
\[\begin{split}
\begin{array}{rl}
\displaystyle%
\min_{\mathbf{x}} &\mathbf{c}' \mathbf{x} \\
\textrm{s.t.} & \mathbf{A}\mathbf{x} = \mathbf{b} \\
~ & \mathbf{x} \in \{0,1 \}^{11}
\end{array}
\end{split}\]
as follows:
\[\begin{split}
\begin{array}{rl}
\displaystyle%
\min_{\mathbf{x}} & \mathbf{c}' \mathbf{x} + \rho (\mathbf{A}\mathbf{x}-\mathbf{b})' (\mathbf{A}\mathbf{x}-\mathbf{b}) \\
\textrm{s.t.} & \mathbf{x} \in \{0,1 \}^{11}
\end{array}
\end{split}\]
Exploiting the fact that \(x^2=x\) for \(x \in \{0,1\}\), we can make the linear terms appear in the diagonal of the \(\mathbf{Q}\) matrix.
\[
\rho(\mathbf{A}\mathbf{x}-\mathbf{b})'(\mathbf{A}\mathbf{x}-\mathbf{b}) = \rho( \mathbf{x}'(\mathbf{A}'\mathbf{A}) \mathbf{x} - 2(\mathbf{A}'\mathbf{b}) \mathbf{x} + \mathbf{b}'\mathbf{b} )
\]
For this problem in particular, one can prove that a reasonable penalization factor is given by \(\rho = \sum_{i=1}^n |c_i| + \epsilon\) with \(\epsilon > 0\).
epsilon = 1
rho = np.sum(np.abs(c)) + epsilon
Q = rho*np.matmul(A.T,A)
Q += np.diag(c)
Q -= rho*2*np.diag(np.matmul(b.T,A))
Beta = rho*np.matmul(b.T,b)
print(Q)
print(Beta)
[[ -46 0 0 48 48 48 0 48 48 48 48]
[ 0 -44 0 48 0 48 48 0 48 48 48]
[ 0 0 -44 0 48 0 48 48 48 48 48]
[ 48 48 0 -92 48 96 48 48 96 96 96]
[ 48 0 48 48 -92 48 48 96 96 96 96]
[ 48 48 0 96 48 -92 48 48 96 96 96]
[ 0 48 48 48 48 48 -91 48 96 96 96]
[ 48 0 48 48 96 48 48 -92 96 96 96]
[ 48 48 48 96 96 96 96 96 -139 144 144]
[ 48 48 48 96 96 96 96 96 144 -138 144]
[ 48 48 48 96 96 96 96 96 144 144 -139]]
144
We can visualize the graph that defines this instance using the Q matrix as the adjacency matrix of a graph.
G = nx.from_numpy_array(Q)
nx.draw(G, with_labels=True)
Let’s define a QUBO model and then solve it using DWaves code for complete enumeration and simulated annealing (eventually with Quantum annealiing too!).
model = dimod.BinaryQuadraticModel.from_qubo(Q, offset=Beta)
print(model)
BinaryQuadraticModel({0: -46.0, 1: -44.0, 2: -44.0, 3: -92.0, 4: -92.0, 5: -92.0, 6: -91.0, 7: -92.0, 8: -139.0, 9: -138.0, 10: -139.0}, {(3, 0): 96.0, (3, 1): 96.0, (4, 0): 96.0, (4, 2): 96.0, (4, 3): 96.0, (5, 0): 96.0, (5, 1): 96.0, (5, 3): 192.0, (5, 4): 96.0, (6, 1): 96.0, (6, 2): 96.0, (6, 3): 96.0, (6, 4): 96.0, (6, 5): 96.0, (7, 0): 96.0, (7, 2): 96.0, (7, 3): 96.0, (7, 4): 192.0, (7, 5): 96.0, (7, 6): 96.0, (8, 0): 96.0, (8, 1): 96.0, (8, 2): 96.0, (8, 3): 192.0, (8, 4): 192.0, (8, 5): 192.0, (8, 6): 192.0, (8, 7): 192.0, (9, 0): 96.0, (9, 1): 96.0, (9, 2): 96.0, (9, 3): 192.0, (9, 4): 192.0, (9, 5): 192.0, (9, 6): 192.0, (9, 7): 192.0, (9, 8): 288.0, (10, 0): 96.0, (10, 1): 96.0, (10, 2): 96.0, (10, 3): 192.0, (10, 4): 192.0, (10, 5): 192.0, (10, 6): 192.0, (10, 7): 192.0, (10, 8): 288.0, (10, 9): 288.0}, 144.0, 'BINARY')
Since the problem is relatively small (11 variables, \(2^{11}=2048\) combinations), we can afford to enumerate all the solutions.
exactSampler = dimod.reference.samplers.ExactSolver()
exactSamples = exactSampler.sample(model)
# Some useful functions to get plots
def plot_enumerate(results, title=None):
plt.figure()
energies = [datum.energy for datum in results.data(
['energy'], sorted_by='energy')]
if results.vartype == 'Vartype.BINARY':
samples = [''.join(c for c in str(datum.sample.values()).strip(
', ') if c.isdigit()) for datum in results.data(['sample'], sorted_by=None)]
plt.xlabel('bitstring for solution')
else:
samples = np.arange(len(energies))
plt.xlabel('solution')
plt.bar(samples,energies)
plt.xticks(rotation=90)
plt.ylabel('Energy')
plt.title(str(title))
print("minimum energy:", min(energies))
def plot_samples(results, title=None):
plt.figure()
if results.vartype == 'Vartype.BINARY':
samples = [''.join(c for c in str(datum.sample.values()).strip(
', ') if c.isdigit()) for datum in results.data(['sample'], sorted_by=None)]
plt.xlabel('bitstring for solution')
else:
samples = np.arange(len(energies))
plt.xlabel('solution')
counts = Counter(samples)
total = len(samples)
for key in counts:
counts[key] /= total
df = pd.DataFrame.from_dict(counts, orient='index').sort_index()
df.plot(kind='bar', legend=None)
plt.xticks(rotation=80)
plt.ylabel('Probabilities')
plt.title(str(title))
plt.show()
print("minimum energy:", min(energies))
def plot_energies(results, title=None, skip=1):
# skip parameter given to avoid putting all xlabels
energies = results.data_vectors['energy']
occurrences = results.data_vectors['num_occurrences']
counts = Counter(energies)
total = sum(occurrences)
counts = {}
for index, energy in enumerate(energies):
if energy in counts.keys():
counts[energy] += occurrences[index]
else:
counts[energy] = occurrences[index]
for key in counts:
counts[key] /= total
df = pd.DataFrame.from_dict(counts, orient='index').sort_index()
ax = df.plot(kind='bar', legend=None)
plt.xlabel('Energy')
plt.ylabel('Probabilities')
# Plot only a subset of xlabels (every skip steps)
for i, label in enumerate(ax.get_xticklabels()):
if i % 10 != 0:
label.set_visible(False)
plt.title(str(title))
plt.show()
print("minimum energy:", min(energies))
plot_enumerate(exactSamples, title='Enumerate all solutions')
plot_energies(exactSamples, title='Enumerate all solutions', skip=10)
minimum energy: 5.0
minimum energy: 5.0
Let’s now solve this QUBO via traditional Integer Programming.
# We do not need to worry about the tranformation to QUBO since dimod takes care of it
Q, c = model.to_qubo()
# Define the model
model_pyo = pyo.ConcreteModel(name='QUBO example as an IP, 47-779/785 QuIPML')
I = range(len(model))
J = range(len(model))
#Define the original variables
model_pyo.x = pyo.Var(I, domain=pyo.Binary)
# Define the edges variables
model_pyo.y = pyo.Var(I, J, domain=pyo.Binary)
obj_expr = c
# add model constraints
model_pyo.c1 = pyo.ConstraintList()
model_pyo.c2 = pyo.ConstraintList()
model_pyo.c3 = pyo.ConstraintList()
for (i,j) in Q.keys():
if i != j:
model_pyo.c1.add(model_pyo.y[i,j] >= model_pyo.x[i] + model_pyo.x[j] - 1)
model_pyo.c2.add(model_pyo.y[i,j] <= model_pyo.x[i])
model_pyo.c3.add(model_pyo.y[i,j] <= model_pyo.x[j])
obj_expr += Q[i,j]*model_pyo.y[i,j]
else:
obj_expr += Q[i,j]*model_pyo.x[i]
# Define the objective function
model_pyo.objective = pyo.Objective(expr = obj_expr, sense=pyo.minimize)
# Print the model
model_pyo.display()
Model 'QUBO example as an IP, 47-779/785 QuIPML'
Variables:
x : Size=11, Index={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Key : Lower : Value : Upper : Fixed : Stale : Domain
0 : 0 : None : 1 : False : True : Binary
1 : 0 : None : 1 : False : True : Binary
2 : 0 : None : 1 : False : True : Binary
3 : 0 : None : 1 : False : True : Binary
4 : 0 : None : 1 : False : True : Binary
5 : 0 : None : 1 : False : True : Binary
6 : 0 : None : 1 : False : True : Binary
7 : 0 : None : 1 : False : True : Binary
8 : 0 : None : 1 : False : True : Binary
9 : 0 : None : 1 : False : True : Binary
10 : 0 : None : 1 : False : True : Binary
y : Size=121, Index={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}*{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Key : Lower : Value : Upper : Fixed : Stale : Domain
(0, 0) : 0 : None : 1 : False : True : Binary
(0, 1) : 0 : None : 1 : False : True : Binary
(0, 2) : 0 : None : 1 : False : True : Binary
(0, 3) : 0 : None : 1 : False : True : Binary
(0, 4) : 0 : None : 1 : False : True : Binary
(0, 5) : 0 : None : 1 : False : True : Binary
(0, 6) : 0 : None : 1 : False : True : Binary
(0, 7) : 0 : None : 1 : False : True : Binary
(0, 8) : 0 : None : 1 : False : True : Binary
(0, 9) : 0 : None : 1 : False : True : Binary
(0, 10) : 0 : None : 1 : False : True : Binary
(1, 0) : 0 : None : 1 : False : True : Binary
(1, 1) : 0 : None : 1 : False : True : Binary
(1, 2) : 0 : None : 1 : False : True : Binary
(1, 3) : 0 : None : 1 : False : True : Binary
(1, 4) : 0 : None : 1 : False : True : Binary
(1, 5) : 0 : None : 1 : False : True : Binary
(1, 6) : 0 : None : 1 : False : True : Binary
(1, 7) : 0 : None : 1 : False : True : Binary
(1, 8) : 0 : None : 1 : False : True : Binary
(1, 9) : 0 : None : 1 : False : True : Binary
(1, 10) : 0 : None : 1 : False : True : Binary
(2, 0) : 0 : None : 1 : False : True : Binary
(2, 1) : 0 : None : 1 : False : True : Binary
(2, 2) : 0 : None : 1 : False : True : Binary
(2, 3) : 0 : None : 1 : False : True : Binary
(2, 4) : 0 : None : 1 : False : True : Binary
(2, 5) : 0 : None : 1 : False : True : Binary
(2, 6) : 0 : None : 1 : False : True : Binary
(2, 7) : 0 : None : 1 : False : True : Binary
(2, 8) : 0 : None : 1 : False : True : Binary
(2, 9) : 0 : None : 1 : False : True : Binary
(2, 10) : 0 : None : 1 : False : True : Binary
(3, 0) : 0 : None : 1 : False : True : Binary
(3, 1) : 0 : None : 1 : False : True : Binary
(3, 2) : 0 : None : 1 : False : True : Binary
(3, 3) : 0 : None : 1 : False : True : Binary
(3, 4) : 0 : None : 1 : False : True : Binary
(3, 5) : 0 : None : 1 : False : True : Binary
(3, 6) : 0 : None : 1 : False : True : Binary
(3, 7) : 0 : None : 1 : False : True : Binary
(3, 8) : 0 : None : 1 : False : True : Binary
(3, 9) : 0 : None : 1 : False : True : Binary
(3, 10) : 0 : None : 1 : False : True : Binary
(4, 0) : 0 : None : 1 : False : True : Binary
(4, 1) : 0 : None : 1 : False : True : Binary
(4, 2) : 0 : None : 1 : False : True : Binary
(4, 3) : 0 : None : 1 : False : True : Binary
(4, 4) : 0 : None : 1 : False : True : Binary
(4, 5) : 0 : None : 1 : False : True : Binary
(4, 6) : 0 : None : 1 : False : True : Binary
(4, 7) : 0 : None : 1 : False : True : Binary
(4, 8) : 0 : None : 1 : False : True : Binary
(4, 9) : 0 : None : 1 : False : True : Binary
(4, 10) : 0 : None : 1 : False : True : Binary
(5, 0) : 0 : None : 1 : False : True : Binary
(5, 1) : 0 : None : 1 : False : True : Binary
(5, 2) : 0 : None : 1 : False : True : Binary
(5, 3) : 0 : None : 1 : False : True : Binary
(5, 4) : 0 : None : 1 : False : True : Binary
(5, 5) : 0 : None : 1 : False : True : Binary
(5, 6) : 0 : None : 1 : False : True : Binary
(5, 7) : 0 : None : 1 : False : True : Binary
(5, 8) : 0 : None : 1 : False : True : Binary
(5, 9) : 0 : None : 1 : False : True : Binary
(5, 10) : 0 : None : 1 : False : True : Binary
(6, 0) : 0 : None : 1 : False : True : Binary
(6, 1) : 0 : None : 1 : False : True : Binary
(6, 2) : 0 : None : 1 : False : True : Binary
(6, 3) : 0 : None : 1 : False : True : Binary
(6, 4) : 0 : None : 1 : False : True : Binary
(6, 5) : 0 : None : 1 : False : True : Binary
(6, 6) : 0 : None : 1 : False : True : Binary
(6, 7) : 0 : None : 1 : False : True : Binary
(6, 8) : 0 : None : 1 : False : True : Binary
(6, 9) : 0 : None : 1 : False : True : Binary
(6, 10) : 0 : None : 1 : False : True : Binary
(7, 0) : 0 : None : 1 : False : True : Binary
(7, 1) : 0 : None : 1 : False : True : Binary
(7, 2) : 0 : None : 1 : False : True : Binary
(7, 3) : 0 : None : 1 : False : True : Binary
(7, 4) : 0 : None : 1 : False : True : Binary
(7, 5) : 0 : None : 1 : False : True : Binary
(7, 6) : 0 : None : 1 : False : True : Binary
(7, 7) : 0 : None : 1 : False : True : Binary
(7, 8) : 0 : None : 1 : False : True : Binary
(7, 9) : 0 : None : 1 : False : True : Binary
(7, 10) : 0 : None : 1 : False : True : Binary
(8, 0) : 0 : None : 1 : False : True : Binary
(8, 1) : 0 : None : 1 : False : True : Binary
(8, 2) : 0 : None : 1 : False : True : Binary
(8, 3) : 0 : None : 1 : False : True : Binary
(8, 4) : 0 : None : 1 : False : True : Binary
(8, 5) : 0 : None : 1 : False : True : Binary
(8, 6) : 0 : None : 1 : False : True : Binary
(8, 7) : 0 : None : 1 : False : True : Binary
(8, 8) : 0 : None : 1 : False : True : Binary
(8, 9) : 0 : None : 1 : False : True : Binary
(8, 10) : 0 : None : 1 : False : True : Binary
(9, 0) : 0 : None : 1 : False : True : Binary
(9, 1) : 0 : None : 1 : False : True : Binary
(9, 2) : 0 : None : 1 : False : True : Binary
(9, 3) : 0 : None : 1 : False : True : Binary
(9, 4) : 0 : None : 1 : False : True : Binary
(9, 5) : 0 : None : 1 : False : True : Binary
(9, 6) : 0 : None : 1 : False : True : Binary
(9, 7) : 0 : None : 1 : False : True : Binary
(9, 8) : 0 : None : 1 : False : True : Binary
(9, 9) : 0 : None : 1 : False : True : Binary
(9, 10) : 0 : None : 1 : False : True : Binary
(10, 0) : 0 : None : 1 : False : True : Binary
(10, 1) : 0 : None : 1 : False : True : Binary
(10, 2) : 0 : None : 1 : False : True : Binary
(10, 3) : 0 : None : 1 : False : True : Binary
(10, 4) : 0 : None : 1 : False : True : Binary
(10, 5) : 0 : None : 1 : False : True : Binary
(10, 6) : 0 : None : 1 : False : True : Binary
(10, 7) : 0 : None : 1 : False : True : Binary
(10, 8) : 0 : None : 1 : False : True : Binary
(10, 9) : 0 : None : 1 : False : True : Binary
(10, 10) : 0 : None : 1 : False : True : Binary
Objectives:
objective : Size=1, Index=None, Active=True
ERROR: evaluating object as numeric value: y[3,0]
(object: <class 'pyomo.core.base.var.VarData'>)
No value for uninitialized NumericValue object y[3,0]
ERROR: evaluating object as numeric value: objective
(object: <class 'pyomo.core.base.objective.ScalarObjective'>)
No value for uninitialized NumericValue object y[3,0]
Key : Active : Value
None : None : None
Constraints:
c1 : Size=47
Key : Lower : Body : Upper
1 : None : None : 0.0
2 : None : None : 0.0
3 : None : None : 0.0
4 : None : None : 0.0
5 : None : None : 0.0
6 : None : None : 0.0
7 : None : None : 0.0
8 : None : None : 0.0
9 : None : None : 0.0
10 : None : None : 0.0
11 : None : None : 0.0
12 : None : None : 0.0
13 : None : None : 0.0
14 : None : None : 0.0
15 : None : None : 0.0
16 : None : None : 0.0
17 : None : None : 0.0
18 : None : None : 0.0
19 : None : None : 0.0
20 : None : None : 0.0
21 : None : None : 0.0
22 : None : None : 0.0
23 : None : None : 0.0
24 : None : None : 0.0
25 : None : None : 0.0
26 : None : None : 0.0
27 : None : None : 0.0
28 : None : None : 0.0
29 : None : None : 0.0
30 : None : None : 0.0
31 : None : None : 0.0
32 : None : None : 0.0
33 : None : None : 0.0
34 : None : None : 0.0
35 : None : None : 0.0
36 : None : None : 0.0
37 : None : None : 0.0
38 : None : None : 0.0
39 : None : None : 0.0
40 : None : None : 0.0
41 : None : None : 0.0
42 : None : None : 0.0
43 : None : None : 0.0
44 : None : None : 0.0
45 : None : None : 0.0
46 : None : None : 0.0
47 : None : None : 0.0
c2 : Size=47
Key : Lower : Body : Upper
1 : None : None : 0.0
2 : None : None : 0.0
3 : None : None : 0.0
4 : None : None : 0.0
5 : None : None : 0.0
6 : None : None : 0.0
7 : None : None : 0.0
8 : None : None : 0.0
9 : None : None : 0.0
10 : None : None : 0.0
11 : None : None : 0.0
12 : None : None : 0.0
13 : None : None : 0.0
14 : None : None : 0.0
15 : None : None : 0.0
16 : None : None : 0.0
17 : None : None : 0.0
18 : None : None : 0.0
19 : None : None : 0.0
20 : None : None : 0.0
21 : None : None : 0.0
22 : None : None : 0.0
23 : None : None : 0.0
24 : None : None : 0.0
25 : None : None : 0.0
26 : None : None : 0.0
27 : None : None : 0.0
28 : None : None : 0.0
29 : None : None : 0.0
30 : None : None : 0.0
31 : None : None : 0.0
32 : None : None : 0.0
33 : None : None : 0.0
34 : None : None : 0.0
35 : None : None : 0.0
36 : None : None : 0.0
37 : None : None : 0.0
38 : None : None : 0.0
39 : None : None : 0.0
40 : None : None : 0.0
41 : None : None : 0.0
42 : None : None : 0.0
43 : None : None : 0.0
44 : None : None : 0.0
45 : None : None : 0.0
46 : None : None : 0.0
47 : None : None : 0.0
c3 : Size=47
Key : Lower : Body : Upper
1 : None : None : 0.0
2 : None : None : 0.0
3 : None : None : 0.0
4 : None : None : 0.0
5 : None : None : 0.0
6 : None : None : 0.0
7 : None : None : 0.0
8 : None : None : 0.0
9 : None : None : 0.0
10 : None : None : 0.0
11 : None : None : 0.0
12 : None : None : 0.0
13 : None : None : 0.0
14 : None : None : 0.0
15 : None : None : 0.0
16 : None : None : 0.0
17 : None : None : 0.0
18 : None : None : 0.0
19 : None : None : 0.0
20 : None : None : 0.0
21 : None : None : 0.0
22 : None : None : 0.0
23 : None : None : 0.0
24 : None : None : 0.0
25 : None : None : 0.0
26 : None : None : 0.0
27 : None : None : 0.0
28 : None : None : 0.0
29 : None : None : 0.0
30 : None : None : 0.0
31 : None : None : 0.0
32 : None : None : 0.0
33 : None : None : 0.0
34 : None : None : 0.0
35 : None : None : 0.0
36 : None : None : 0.0
37 : None : None : 0.0
38 : None : None : 0.0
39 : None : None : 0.0
40 : None : None : 0.0
41 : None : None : 0.0
42 : None : None : 0.0
43 : None : None : 0.0
44 : None : None : 0.0
45 : None : None : 0.0
46 : None : None : 0.0
47 : None : None : 0.0
Let’s install the MIP solver GLPK
# Let's install the LP/MIP solver GLPK
if IN_COLAB:
!apt-get install -y -qq glpk-utils
# Define the solver GLPK
if IN_COLAB:
opt_glpk = pyo.SolverFactory('glpk', executable='/usr/bin/glpsol')
else:
opt_glpk = pyo.SolverFactory('glpk')
# Here we could use another solver, e.g. gurobi or cplex
# opt_gurobi = pyo.SolverFactory('gurobi')
# We obtain the solution with GLPK
result_obj = opt_glpk.solve(model_pyo, tee=False)
model_pyo.display()
Model 'QUBO example as an IP, 47-779/785 QuIPML'
Variables:
x : Size=11, Index={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Key : Lower : Value : Upper : Fixed : Stale : Domain
0 : 0 : 0.0 : 1 : False : False : Binary
1 : 0 : 0.0 : 1 : False : False : Binary
2 : 0 : 0.0 : 1 : False : False : Binary
3 : 0 : 0.0 : 1 : False : False : Binary
4 : 0 : 0.0 : 1 : False : False : Binary
5 : 0 : 0.0 : 1 : False : False : Binary
6 : 0 : 0.0 : 1 : False : False : Binary
7 : 0 : 0.0 : 1 : False : False : Binary
8 : 0 : 0.0 : 1 : False : False : Binary
9 : 0 : 0.0 : 1 : False : False : Binary
10 : 0 : 1.0 : 1 : False : False : Binary
y : Size=121, Index={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}*{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Key : Lower : Value : Upper : Fixed : Stale : Domain
(0, 0) : 0 : None : 1 : False : True : Binary
(0, 1) : 0 : None : 1 : False : True : Binary
(0, 2) : 0 : None : 1 : False : True : Binary
(0, 3) : 0 : None : 1 : False : True : Binary
(0, 4) : 0 : None : 1 : False : True : Binary
(0, 5) : 0 : None : 1 : False : True : Binary
(0, 6) : 0 : None : 1 : False : True : Binary
(0, 7) : 0 : None : 1 : False : True : Binary
(0, 8) : 0 : None : 1 : False : True : Binary
(0, 9) : 0 : None : 1 : False : True : Binary
(0, 10) : 0 : None : 1 : False : True : Binary
(1, 0) : 0 : None : 1 : False : True : Binary
(1, 1) : 0 : None : 1 : False : True : Binary
(1, 2) : 0 : None : 1 : False : True : Binary
(1, 3) : 0 : None : 1 : False : True : Binary
(1, 4) : 0 : None : 1 : False : True : Binary
(1, 5) : 0 : None : 1 : False : True : Binary
(1, 6) : 0 : None : 1 : False : True : Binary
(1, 7) : 0 : None : 1 : False : True : Binary
(1, 8) : 0 : None : 1 : False : True : Binary
(1, 9) : 0 : None : 1 : False : True : Binary
(1, 10) : 0 : None : 1 : False : True : Binary
(2, 0) : 0 : None : 1 : False : True : Binary
(2, 1) : 0 : None : 1 : False : True : Binary
(2, 2) : 0 : None : 1 : False : True : Binary
(2, 3) : 0 : None : 1 : False : True : Binary
(2, 4) : 0 : None : 1 : False : True : Binary
(2, 5) : 0 : None : 1 : False : True : Binary
(2, 6) : 0 : None : 1 : False : True : Binary
(2, 7) : 0 : None : 1 : False : True : Binary
(2, 8) : 0 : None : 1 : False : True : Binary
(2, 9) : 0 : None : 1 : False : True : Binary
(2, 10) : 0 : None : 1 : False : True : Binary
(3, 0) : 0 : 0.0 : 1 : False : False : Binary
(3, 1) : 0 : 0.0 : 1 : False : False : Binary
(3, 2) : 0 : None : 1 : False : True : Binary
(3, 3) : 0 : None : 1 : False : True : Binary
(3, 4) : 0 : None : 1 : False : True : Binary
(3, 5) : 0 : None : 1 : False : True : Binary
(3, 6) : 0 : None : 1 : False : True : Binary
(3, 7) : 0 : None : 1 : False : True : Binary
(3, 8) : 0 : None : 1 : False : True : Binary
(3, 9) : 0 : None : 1 : False : True : Binary
(3, 10) : 0 : None : 1 : False : True : Binary
(4, 0) : 0 : 0.0 : 1 : False : False : Binary
(4, 1) : 0 : None : 1 : False : True : Binary
(4, 2) : 0 : 0.0 : 1 : False : False : Binary
(4, 3) : 0 : 0.0 : 1 : False : False : Binary
(4, 4) : 0 : None : 1 : False : True : Binary
(4, 5) : 0 : None : 1 : False : True : Binary
(4, 6) : 0 : None : 1 : False : True : Binary
(4, 7) : 0 : None : 1 : False : True : Binary
(4, 8) : 0 : None : 1 : False : True : Binary
(4, 9) : 0 : None : 1 : False : True : Binary
(4, 10) : 0 : None : 1 : False : True : Binary
(5, 0) : 0 : 0.0 : 1 : False : False : Binary
(5, 1) : 0 : 0.0 : 1 : False : False : Binary
(5, 2) : 0 : None : 1 : False : True : Binary
(5, 3) : 0 : 0.0 : 1 : False : False : Binary
(5, 4) : 0 : 0.0 : 1 : False : False : Binary
(5, 5) : 0 : None : 1 : False : True : Binary
(5, 6) : 0 : None : 1 : False : True : Binary
(5, 7) : 0 : None : 1 : False : True : Binary
(5, 8) : 0 : None : 1 : False : True : Binary
(5, 9) : 0 : None : 1 : False : True : Binary
(5, 10) : 0 : None : 1 : False : True : Binary
(6, 0) : 0 : None : 1 : False : True : Binary
(6, 1) : 0 : 0.0 : 1 : False : False : Binary
(6, 2) : 0 : 0.0 : 1 : False : False : Binary
(6, 3) : 0 : 0.0 : 1 : False : False : Binary
(6, 4) : 0 : 0.0 : 1 : False : False : Binary
(6, 5) : 0 : 0.0 : 1 : False : False : Binary
(6, 6) : 0 : None : 1 : False : True : Binary
(6, 7) : 0 : None : 1 : False : True : Binary
(6, 8) : 0 : None : 1 : False : True : Binary
(6, 9) : 0 : None : 1 : False : True : Binary
(6, 10) : 0 : None : 1 : False : True : Binary
(7, 0) : 0 : 0.0 : 1 : False : False : Binary
(7, 1) : 0 : None : 1 : False : True : Binary
(7, 2) : 0 : 0.0 : 1 : False : False : Binary
(7, 3) : 0 : 0.0 : 1 : False : False : Binary
(7, 4) : 0 : 0.0 : 1 : False : False : Binary
(7, 5) : 0 : 0.0 : 1 : False : False : Binary
(7, 6) : 0 : 0.0 : 1 : False : False : Binary
(7, 7) : 0 : None : 1 : False : True : Binary
(7, 8) : 0 : None : 1 : False : True : Binary
(7, 9) : 0 : None : 1 : False : True : Binary
(7, 10) : 0 : None : 1 : False : True : Binary
(8, 0) : 0 : 0.0 : 1 : False : False : Binary
(8, 1) : 0 : 0.0 : 1 : False : False : Binary
(8, 2) : 0 : 0.0 : 1 : False : False : Binary
(8, 3) : 0 : 0.0 : 1 : False : False : Binary
(8, 4) : 0 : 0.0 : 1 : False : False : Binary
(8, 5) : 0 : 0.0 : 1 : False : False : Binary
(8, 6) : 0 : 0.0 : 1 : False : False : Binary
(8, 7) : 0 : 0.0 : 1 : False : False : Binary
(8, 8) : 0 : None : 1 : False : True : Binary
(8, 9) : 0 : None : 1 : False : True : Binary
(8, 10) : 0 : None : 1 : False : True : Binary
(9, 0) : 0 : 0.0 : 1 : False : False : Binary
(9, 1) : 0 : 0.0 : 1 : False : False : Binary
(9, 2) : 0 : 0.0 : 1 : False : False : Binary
(9, 3) : 0 : 0.0 : 1 : False : False : Binary
(9, 4) : 0 : 0.0 : 1 : False : False : Binary
(9, 5) : 0 : 0.0 : 1 : False : False : Binary
(9, 6) : 0 : 0.0 : 1 : False : False : Binary
(9, 7) : 0 : 0.0 : 1 : False : False : Binary
(9, 8) : 0 : 0.0 : 1 : False : False : Binary
(9, 9) : 0 : None : 1 : False : True : Binary
(9, 10) : 0 : None : 1 : False : True : Binary
(10, 0) : 0 : 0.0 : 1 : False : False : Binary
(10, 1) : 0 : 0.0 : 1 : False : False : Binary
(10, 2) : 0 : 0.0 : 1 : False : False : Binary
(10, 3) : 0 : 0.0 : 1 : False : False : Binary
(10, 4) : 0 : 0.0 : 1 : False : False : Binary
(10, 5) : 0 : 0.0 : 1 : False : False : Binary
(10, 6) : 0 : 0.0 : 1 : False : False : Binary
(10, 7) : 0 : 0.0 : 1 : False : False : Binary
(10, 8) : 0 : 0.0 : 1 : False : False : Binary
(10, 9) : 0 : 0.0 : 1 : False : False : Binary
(10, 10) : 0 : None : 1 : False : True : Binary
Objectives:
objective : Size=1, Index=None, Active=True
Key : Active : Value
None : True : 5.0
Constraints:
c1 : Size=47
Key : Lower : Body : Upper
1 : None : -1.0 : 0.0
2 : None : -1.0 : 0.0
3 : None : -1.0 : 0.0
4 : None : -1.0 : 0.0
5 : None : -1.0 : 0.0
6 : None : -1.0 : 0.0
7 : None : -1.0 : 0.0
8 : None : -1.0 : 0.0
9 : None : -1.0 : 0.0
10 : None : -1.0 : 0.0
11 : None : -1.0 : 0.0
12 : None : -1.0 : 0.0
13 : None : -1.0 : 0.0
14 : None : -1.0 : 0.0
15 : None : -1.0 : 0.0
16 : None : -1.0 : 0.0
17 : None : -1.0 : 0.0
18 : None : -1.0 : 0.0
19 : None : -1.0 : 0.0
20 : None : -1.0 : 0.0
21 : None : -1.0 : 0.0
22 : None : -1.0 : 0.0
23 : None : -1.0 : 0.0
24 : None : -1.0 : 0.0
25 : None : -1.0 : 0.0
26 : None : -1.0 : 0.0
27 : None : -1.0 : 0.0
28 : None : -1.0 : 0.0
29 : None : -1.0 : 0.0
30 : None : -1.0 : 0.0
31 : None : -1.0 : 0.0
32 : None : -1.0 : 0.0
33 : None : -1.0 : 0.0
34 : None : -1.0 : 0.0
35 : None : -1.0 : 0.0
36 : None : -1.0 : 0.0
37 : None : -1.0 : 0.0
38 : None : 0.0 : 0.0
39 : None : 0.0 : 0.0
40 : None : 0.0 : 0.0
41 : None : 0.0 : 0.0
42 : None : 0.0 : 0.0
43 : None : 0.0 : 0.0
44 : None : 0.0 : 0.0
45 : None : 0.0 : 0.0
46 : None : 0.0 : 0.0
47 : None : 0.0 : 0.0
c2 : Size=47
Key : Lower : Body : Upper
1 : None : 0.0 : 0.0
2 : None : 0.0 : 0.0
3 : None : 0.0 : 0.0
4 : None : 0.0 : 0.0
5 : None : 0.0 : 0.0
6 : None : 0.0 : 0.0
7 : None : 0.0 : 0.0
8 : None : 0.0 : 0.0
9 : None : 0.0 : 0.0
10 : None : 0.0 : 0.0
11 : None : 0.0 : 0.0
12 : None : 0.0 : 0.0
13 : None : 0.0 : 0.0
14 : None : 0.0 : 0.0
15 : None : 0.0 : 0.0
16 : None : 0.0 : 0.0
17 : None : 0.0 : 0.0
18 : None : 0.0 : 0.0
19 : None : 0.0 : 0.0
20 : None : 0.0 : 0.0
21 : None : 0.0 : 0.0
22 : None : 0.0 : 0.0
23 : None : 0.0 : 0.0
24 : None : 0.0 : 0.0
25 : None : 0.0 : 0.0
26 : None : 0.0 : 0.0
27 : None : 0.0 : 0.0
28 : None : 0.0 : 0.0
29 : None : 0.0 : 0.0
30 : None : 0.0 : 0.0
31 : None : 0.0 : 0.0
32 : None : 0.0 : 0.0
33 : None : 0.0 : 0.0
34 : None : 0.0 : 0.0
35 : None : 0.0 : 0.0
36 : None : 0.0 : 0.0
37 : None : 0.0 : 0.0
38 : None : -1.0 : 0.0
39 : None : -1.0 : 0.0
40 : None : -1.0 : 0.0
41 : None : -1.0 : 0.0
42 : None : -1.0 : 0.0
43 : None : -1.0 : 0.0
44 : None : -1.0 : 0.0
45 : None : -1.0 : 0.0
46 : None : -1.0 : 0.0
47 : None : -1.0 : 0.0
c3 : Size=47
Key : Lower : Body : Upper
1 : None : 0.0 : 0.0
2 : None : 0.0 : 0.0
3 : None : 0.0 : 0.0
4 : None : 0.0 : 0.0
5 : None : 0.0 : 0.0
6 : None : 0.0 : 0.0
7 : None : 0.0 : 0.0
8 : None : 0.0 : 0.0
9 : None : 0.0 : 0.0
10 : None : 0.0 : 0.0
11 : None : 0.0 : 0.0
12 : None : 0.0 : 0.0
13 : None : 0.0 : 0.0
14 : None : 0.0 : 0.0
15 : None : 0.0 : 0.0
16 : None : 0.0 : 0.0
17 : None : 0.0 : 0.0
18 : None : 0.0 : 0.0
19 : None : 0.0 : 0.0
20 : None : 0.0 : 0.0
21 : None : 0.0 : 0.0
22 : None : 0.0 : 0.0
23 : None : 0.0 : 0.0
24 : None : 0.0 : 0.0
25 : None : 0.0 : 0.0
26 : None : 0.0 : 0.0
27 : None : 0.0 : 0.0
28 : None : 0.0 : 0.0
29 : None : 0.0 : 0.0
30 : None : 0.0 : 0.0
31 : None : 0.0 : 0.0
32 : None : 0.0 : 0.0
33 : None : 0.0 : 0.0
34 : None : 0.0 : 0.0
35 : None : 0.0 : 0.0
36 : None : 0.0 : 0.0
37 : None : 0.0 : 0.0
38 : None : 0.0 : 0.0
39 : None : 0.0 : 0.0
40 : None : 0.0 : 0.0
41 : None : 0.0 : 0.0
42 : None : 0.0 : 0.0
43 : None : 0.0 : 0.0
44 : None : 0.0 : 0.0
45 : None : 0.0 : 0.0
46 : None : 0.0 : 0.0
47 : None : 0.0 : 0.0
We observe that the optimal solution of this problem is \(x_{8} = 1, 0\) otherwise, leading to an objective of \(5\). Notice that this problem has a degenerate optimal solution given that \(x_{10} = 1, 0\) otherwise also leads to the same solution.
Ising model#
This notebook will explain the basics of the Ising model. In order to implement the different Ising Models we will use D-Wave’s packages dimod and neal, for defining the Ising model and solving it with simulated annealing, respectively. When posing the problems as Integer programs, we will model using Pyomo, an open-source Python package, which provides a flexible access to different solvers and a general modeling framework for linear and nonlinear integer programs. The examples solved here will make use of open-source solver GLPK for mixed-integer linear programming.
Problem statement#
We pose the Ising problem as the following optimization problem:
\[
\min_{\sigma \in \{ -1,+1 \}^n} H(\sigma) =\min_{\sigma \in \{ -1,+1 \}^n} \sum_{(ij) \in E(G)} J_{ij}\sigma_i\sigma_j + \sum_{i \in V(G)}h_i\sigma_i + c_I
\]
where we optimize over spins \(\sigma \in \{ -1,+1 \}^n\), on a constrained graph \(G(V,E)\), where the quadratic coefficients are \(J_{ij}\) and the linear coefficients are \(h_i\). We also include an arbitrary offset of the Ising model \(c_I\).
Example#
Suppose we have an Ising model defined from
\[\begin{split}
h = \begin{bmatrix}
145.0 \\ 122.0 \\ 122.0 \\ 266.0 \\ 266.0 \\ 266.0 \\ 242.5 \\ 266.0 \\ 386.5 \\ 387.0 \\ 386.5
\end{bmatrix},
J = \begin{bmatrix}
0 & 0 & 0 & 24 & 24 & 24 & 24 & 24 & 24 & 24 & 24\\
0 & 0 & 0 & 24 & 0 & 24 & 24 & 24 & 24 & 24 & 24\\
0 & 0 & 0 & 0 & 24 & 0 & 24 & 24 & 24 & 24 & 24\\
0 & 0 & 0 & 0 & 24 & 48 & 24 & 24 & 48 & 48 & 48\\
0 & 0 & 0 & 0 & 0 & 24 & 24 & 48 & 48 & 48 & 48\\
0 & 0 & 0 & 0 & 0 & 0 & 24 & 24 & 48 & 48 & 48\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 24 & 48 & 48 & 48\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 48 & 48 & 48\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 72 & 72\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 72\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
\end{bmatrix} \text{ and }
\beta = 1319.5
\end{split}\]
Let’s solve this problem
# These could also be simple lists and numpy matrices
h = {0: 145.0, 1: 122.0, 2: 122.0, 3: 266.0, 4: 266.0, 5: 266.0, 6: 242.5, 7: 266.0, 8: 386.5, 9: 387.0, 10: 386.5}
J = {(0, 3): 24.0, (0, 4): 24.0, (0, 5): 24.0, (0, 7): 24.0, (0, 8): 24.0, (0, 9): 24.0, (0, 10): 24.0, (1, 3): 24.0, (1, 5): 24.0, (1, 6): 24.0, (1, 8): 24.0, (1, 9): 24.0, (1, 10): 24.0, (2, 4): 24.0, (2, 6): 24.0, (2, 7): 24.0, (2, 8): 24.0, (2, 9): 24.0, (2, 10): 24.0, (3, 4): 24.0, (3, 5): 48.0, (3, 6): 24.0, (3, 7): 24.0, (3, 8): 48.0, (3, 9): 48.0, (3, 10): 48.0, (4, 5): 24.0, (4, 6): 24.0, (4, 7): 48.0, (4, 8): 48.0, (4, 9): 48.0, (4, 10): 48.0, (5, 6): 24.0, (5, 7): 24.0, (5, 8): 48.0, (5, 9): 48.0, (5, 10): 48.0, (6, 7): 24.0, (6, 8): 48.0, (6, 9): 48.0, (6, 10): 48.0, (7, 8): 48.0, (7, 9): 48.0, (7, 10): 48.0, (8, 9): 72.0, (8, 10): 72.0, (9, 10): 72.0}
cI = 1319.5
model_ising = dimod.BinaryQuadraticModel.from_ising(h, J, offset=cI)
Since the problem is relatively small (11 variables, \(2^{11}=2048\) combinations), we can afford to enumerate all the solutions.
exactSamples = exactSampler.sample(model_ising)
plot_enumerate(exactSamples, title='Enumerate all solutions')
plot_energies(exactSamples, title='Enumerate all solutions')
minimum energy: 5.0
minimum energy: 5.0
Let’s now solve this Ising Model via traditional Integer Programming.
# We do not need to worry about the tranformation from Ising to QUBO since dimod takes care of it
Q, c = model_ising.to_qubo()
# Define the model
model_ising_pyo = pyo.ConcreteModel(name='Ising example as an IP, 47-779/785 QuIPML')
I = range(len(h))
J = range(len(h))
#Define the original variables
model_ising_pyo.x = pyo.Var(I, domain=pyo.Binary)
# Define the edges variables
model_ising_pyo.y = pyo.Var(I, J, domain=pyo.Binary)
obj_expr = c
# add model constraints
model_ising_pyo.c1 = pyo.ConstraintList()
model_ising_pyo.c2 = pyo.ConstraintList()
model_ising_pyo.c3 = pyo.ConstraintList()
for (i,j) in Q.keys():
if i != j:
model_ising_pyo.c1.add(model_ising_pyo.y[i,j] >= model_ising_pyo.x[i] + model_ising_pyo.x[j] - 1)
model_ising_pyo.c2.add(model_ising_pyo.y[i,j] <= model_ising_pyo.x[i])
model_ising_pyo.c3.add(model_ising_pyo.y[i,j] <= model_ising_pyo.x[j])
obj_expr += Q[i,j]*model_ising_pyo.y[i,j]
else:
obj_expr += Q[i,j]*model_ising_pyo.x[i]
# Define the objective function
model_ising_pyo.objective = pyo.Objective(expr = obj_expr, sense=pyo.minimize)
# Print the model
model_ising_pyo.display()
Model 'Ising example as an IP, 47-779/785 QuIPML'
Variables:
x : Size=11, Index={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Key : Lower : Value : Upper : Fixed : Stale : Domain
0 : 0 : None : 1 : False : True : Binary
1 : 0 : None : 1 : False : True : Binary
2 : 0 : None : 1 : False : True : Binary
3 : 0 : None : 1 : False : True : Binary
4 : 0 : None : 1 : False : True : Binary
5 : 0 : None : 1 : False : True : Binary
6 : 0 : None : 1 : False : True : Binary
7 : 0 : None : 1 : False : True : Binary
8 : 0 : None : 1 : False : True : Binary
9 : 0 : None : 1 : False : True : Binary
10 : 0 : None : 1 : False : True : Binary
y : Size=121, Index={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}*{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Key : Lower : Value : Upper : Fixed : Stale : Domain
(0, 0) : 0 : None : 1 : False : True : Binary
(0, 1) : 0 : None : 1 : False : True : Binary
(0, 2) : 0 : None : 1 : False : True : Binary
(0, 3) : 0 : None : 1 : False : True : Binary
(0, 4) : 0 : None : 1 : False : True : Binary
(0, 5) : 0 : None : 1 : False : True : Binary
(0, 6) : 0 : None : 1 : False : True : Binary
(0, 7) : 0 : None : 1 : False : True : Binary
(0, 8) : 0 : None : 1 : False : True : Binary
(0, 9) : 0 : None : 1 : False : True : Binary
(0, 10) : 0 : None : 1 : False : True : Binary
(1, 0) : 0 : None : 1 : False : True : Binary
(1, 1) : 0 : None : 1 : False : True : Binary
(1, 2) : 0 : None : 1 : False : True : Binary
(1, 3) : 0 : None : 1 : False : True : Binary
(1, 4) : 0 : None : 1 : False : True : Binary
(1, 5) : 0 : None : 1 : False : True : Binary
(1, 6) : 0 : None : 1 : False : True : Binary
(1, 7) : 0 : None : 1 : False : True : Binary
(1, 8) : 0 : None : 1 : False : True : Binary
(1, 9) : 0 : None : 1 : False : True : Binary
(1, 10) : 0 : None : 1 : False : True : Binary
(2, 0) : 0 : None : 1 : False : True : Binary
(2, 1) : 0 : None : 1 : False : True : Binary
(2, 2) : 0 : None : 1 : False : True : Binary
(2, 3) : 0 : None : 1 : False : True : Binary
(2, 4) : 0 : None : 1 : False : True : Binary
(2, 5) : 0 : None : 1 : False : True : Binary
(2, 6) : 0 : None : 1 : False : True : Binary
(2, 7) : 0 : None : 1 : False : True : Binary
(2, 8) : 0 : None : 1 : False : True : Binary
(2, 9) : 0 : None : 1 : False : True : Binary
(2, 10) : 0 : None : 1 : False : True : Binary
(3, 0) : 0 : None : 1 : False : True : Binary
(3, 1) : 0 : None : 1 : False : True : Binary
(3, 2) : 0 : None : 1 : False : True : Binary
(3, 3) : 0 : None : 1 : False : True : Binary
(3, 4) : 0 : None : 1 : False : True : Binary
(3, 5) : 0 : None : 1 : False : True : Binary
(3, 6) : 0 : None : 1 : False : True : Binary
(3, 7) : 0 : None : 1 : False : True : Binary
(3, 8) : 0 : None : 1 : False : True : Binary
(3, 9) : 0 : None : 1 : False : True : Binary
(3, 10) : 0 : None : 1 : False : True : Binary
(4, 0) : 0 : None : 1 : False : True : Binary
(4, 1) : 0 : None : 1 : False : True : Binary
(4, 2) : 0 : None : 1 : False : True : Binary
(4, 3) : 0 : None : 1 : False : True : Binary
(4, 4) : 0 : None : 1 : False : True : Binary
(4, 5) : 0 : None : 1 : False : True : Binary
(4, 6) : 0 : None : 1 : False : True : Binary
(4, 7) : 0 : None : 1 : False : True : Binary
(4, 8) : 0 : None : 1 : False : True : Binary
(4, 9) : 0 : None : 1 : False : True : Binary
(4, 10) : 0 : None : 1 : False : True : Binary
(5, 0) : 0 : None : 1 : False : True : Binary
(5, 1) : 0 : None : 1 : False : True : Binary
(5, 2) : 0 : None : 1 : False : True : Binary
(5, 3) : 0 : None : 1 : False : True : Binary
(5, 4) : 0 : None : 1 : False : True : Binary
(5, 5) : 0 : None : 1 : False : True : Binary
(5, 6) : 0 : None : 1 : False : True : Binary
(5, 7) : 0 : None : 1 : False : True : Binary
(5, 8) : 0 : None : 1 : False : True : Binary
(5, 9) : 0 : None : 1 : False : True : Binary
(5, 10) : 0 : None : 1 : False : True : Binary
(6, 0) : 0 : None : 1 : False : True : Binary
(6, 1) : 0 : None : 1 : False : True : Binary
(6, 2) : 0 : None : 1 : False : True : Binary
(6, 3) : 0 : None : 1 : False : True : Binary
(6, 4) : 0 : None : 1 : False : True : Binary
(6, 5) : 0 : None : 1 : False : True : Binary
(6, 6) : 0 : None : 1 : False : True : Binary
(6, 7) : 0 : None : 1 : False : True : Binary
(6, 8) : 0 : None : 1 : False : True : Binary
(6, 9) : 0 : None : 1 : False : True : Binary
(6, 10) : 0 : None : 1 : False : True : Binary
(7, 0) : 0 : None : 1 : False : True : Binary
(7, 1) : 0 : None : 1 : False : True : Binary
(7, 2) : 0 : None : 1 : False : True : Binary
(7, 3) : 0 : None : 1 : False : True : Binary
(7, 4) : 0 : None : 1 : False : True : Binary
(7, 5) : 0 : None : 1 : False : True : Binary
(7, 6) : 0 : None : 1 : False : True : Binary
(7, 7) : 0 : None : 1 : False : True : Binary
(7, 8) : 0 : None : 1 : False : True : Binary
(7, 9) : 0 : None : 1 : False : True : Binary
(7, 10) : 0 : None : 1 : False : True : Binary
(8, 0) : 0 : None : 1 : False : True : Binary
(8, 1) : 0 : None : 1 : False : True : Binary
(8, 2) : 0 : None : 1 : False : True : Binary
(8, 3) : 0 : None : 1 : False : True : Binary
(8, 4) : 0 : None : 1 : False : True : Binary
(8, 5) : 0 : None : 1 : False : True : Binary
(8, 6) : 0 : None : 1 : False : True : Binary
(8, 7) : 0 : None : 1 : False : True : Binary
(8, 8) : 0 : None : 1 : False : True : Binary
(8, 9) : 0 : None : 1 : False : True : Binary
(8, 10) : 0 : None : 1 : False : True : Binary
(9, 0) : 0 : None : 1 : False : True : Binary
(9, 1) : 0 : None : 1 : False : True : Binary
(9, 2) : 0 : None : 1 : False : True : Binary
(9, 3) : 0 : None : 1 : False : True : Binary
(9, 4) : 0 : None : 1 : False : True : Binary
(9, 5) : 0 : None : 1 : False : True : Binary
(9, 6) : 0 : None : 1 : False : True : Binary
(9, 7) : 0 : None : 1 : False : True : Binary
(9, 8) : 0 : None : 1 : False : True : Binary
(9, 9) : 0 : None : 1 : False : True : Binary
(9, 10) : 0 : None : 1 : False : True : Binary
(10, 0) : 0 : None : 1 : False : True : Binary
(10, 1) : 0 : None : 1 : False : True : Binary
(10, 2) : 0 : None : 1 : False : True : Binary
(10, 3) : 0 : None : 1 : False : True : Binary
(10, 4) : 0 : None : 1 : False : True : Binary
(10, 5) : 0 : None : 1 : False : True : Binary
(10, 6) : 0 : None : 1 : False : True : Binary
(10, 7) : 0 : None : 1 : False : True : Binary
(10, 8) : 0 : None : 1 : False : True : Binary
(10, 9) : 0 : None : 1 : False : True : Binary
(10, 10) : 0 : None : 1 : False : True : Binary
Objectives:
objective : Size=1, Index=None, Active=True
ERROR: evaluating object as numeric value: y[3,0]
(object: <class 'pyomo.core.base.var.VarData'>)
No value for uninitialized NumericValue object y[3,0]
ERROR: evaluating object as numeric value: objective
(object: <class 'pyomo.core.base.objective.ScalarObjective'>)
No value for uninitialized NumericValue object y[3,0]
Key : Active : Value
None : None : None
Constraints:
c1 : Size=47
Key : Lower : Body : Upper
1 : None : None : 0.0
2 : None : None : 0.0
3 : None : None : 0.0
4 : None : None : 0.0
5 : None : None : 0.0
6 : None : None : 0.0
7 : None : None : 0.0
8 : None : None : 0.0
9 : None : None : 0.0
10 : None : None : 0.0
11 : None : None : 0.0
12 : None : None : 0.0
13 : None : None : 0.0
14 : None : None : 0.0
15 : None : None : 0.0
16 : None : None : 0.0
17 : None : None : 0.0
18 : None : None : 0.0
19 : None : None : 0.0
20 : None : None : 0.0
21 : None : None : 0.0
22 : None : None : 0.0
23 : None : None : 0.0
24 : None : None : 0.0
25 : None : None : 0.0
26 : None : None : 0.0
27 : None : None : 0.0
28 : None : None : 0.0
29 : None : None : 0.0
30 : None : None : 0.0
31 : None : None : 0.0
32 : None : None : 0.0
33 : None : None : 0.0
34 : None : None : 0.0
35 : None : None : 0.0
36 : None : None : 0.0
37 : None : None : 0.0
38 : None : None : 0.0
39 : None : None : 0.0
40 : None : None : 0.0
41 : None : None : 0.0
42 : None : None : 0.0
43 : None : None : 0.0
44 : None : None : 0.0
45 : None : None : 0.0
46 : None : None : 0.0
47 : None : None : 0.0
c2 : Size=47
Key : Lower : Body : Upper
1 : None : None : 0.0
2 : None : None : 0.0
3 : None : None : 0.0
4 : None : None : 0.0
5 : None : None : 0.0
6 : None : None : 0.0
7 : None : None : 0.0
8 : None : None : 0.0
9 : None : None : 0.0
10 : None : None : 0.0
11 : None : None : 0.0
12 : None : None : 0.0
13 : None : None : 0.0
14 : None : None : 0.0
15 : None : None : 0.0
16 : None : None : 0.0
17 : None : None : 0.0
18 : None : None : 0.0
19 : None : None : 0.0
20 : None : None : 0.0
21 : None : None : 0.0
22 : None : None : 0.0
23 : None : None : 0.0
24 : None : None : 0.0
25 : None : None : 0.0
26 : None : None : 0.0
27 : None : None : 0.0
28 : None : None : 0.0
29 : None : None : 0.0
30 : None : None : 0.0
31 : None : None : 0.0
32 : None : None : 0.0
33 : None : None : 0.0
34 : None : None : 0.0
35 : None : None : 0.0
36 : None : None : 0.0
37 : None : None : 0.0
38 : None : None : 0.0
39 : None : None : 0.0
40 : None : None : 0.0
41 : None : None : 0.0
42 : None : None : 0.0
43 : None : None : 0.0
44 : None : None : 0.0
45 : None : None : 0.0
46 : None : None : 0.0
47 : None : None : 0.0
c3 : Size=47
Key : Lower : Body : Upper
1 : None : None : 0.0
2 : None : None : 0.0
3 : None : None : 0.0
4 : None : None : 0.0
5 : None : None : 0.0
6 : None : None : 0.0
7 : None : None : 0.0
8 : None : None : 0.0
9 : None : None : 0.0
10 : None : None : 0.0
11 : None : None : 0.0
12 : None : None : 0.0
13 : None : None : 0.0
14 : None : None : 0.0
15 : None : None : 0.0
16 : None : None : 0.0
17 : None : None : 0.0
18 : None : None : 0.0
19 : None : None : 0.0
20 : None : None : 0.0
21 : None : None : 0.0
22 : None : None : 0.0
23 : None : None : 0.0
24 : None : None : 0.0
25 : None : None : 0.0
26 : None : None : 0.0
27 : None : None : 0.0
28 : None : None : 0.0
29 : None : None : 0.0
30 : None : None : 0.0
31 : None : None : 0.0
32 : None : None : 0.0
33 : None : None : 0.0
34 : None : None : 0.0
35 : None : None : 0.0
36 : None : None : 0.0
37 : None : None : 0.0
38 : None : None : 0.0
39 : None : None : 0.0
40 : None : None : 0.0
41 : None : None : 0.0
42 : None : None : 0.0
43 : None : None : 0.0
44 : None : None : 0.0
45 : None : None : 0.0
46 : None : None : 0.0
47 : None : None : 0.0
# We obtain the solution with GLPK
result_obj = opt_glpk.solve(model_ising_pyo, tee=False)
model_ising_pyo.display()
Model 'Ising example as an IP, 47-779/785 QuIPML'
Variables:
x : Size=11, Index={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Key : Lower : Value : Upper : Fixed : Stale : Domain
0 : 0 : 0.0 : 1 : False : False : Binary
1 : 0 : 0.0 : 1 : False : False : Binary
2 : 0 : 0.0 : 1 : False : False : Binary
3 : 0 : 0.0 : 1 : False : False : Binary
4 : 0 : 0.0 : 1 : False : False : Binary
5 : 0 : 0.0 : 1 : False : False : Binary
6 : 0 : 0.0 : 1 : False : False : Binary
7 : 0 : 0.0 : 1 : False : False : Binary
8 : 0 : 0.0 : 1 : False : False : Binary
9 : 0 : 0.0 : 1 : False : False : Binary
10 : 0 : 1.0 : 1 : False : False : Binary
y : Size=121, Index={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}*{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Key : Lower : Value : Upper : Fixed : Stale : Domain
(0, 0) : 0 : None : 1 : False : True : Binary
(0, 1) : 0 : None : 1 : False : True : Binary
(0, 2) : 0 : None : 1 : False : True : Binary
(0, 3) : 0 : None : 1 : False : True : Binary
(0, 4) : 0 : None : 1 : False : True : Binary
(0, 5) : 0 : None : 1 : False : True : Binary
(0, 6) : 0 : None : 1 : False : True : Binary
(0, 7) : 0 : None : 1 : False : True : Binary
(0, 8) : 0 : None : 1 : False : True : Binary
(0, 9) : 0 : None : 1 : False : True : Binary
(0, 10) : 0 : None : 1 : False : True : Binary
(1, 0) : 0 : None : 1 : False : True : Binary
(1, 1) : 0 : None : 1 : False : True : Binary
(1, 2) : 0 : None : 1 : False : True : Binary
(1, 3) : 0 : 0.0 : 1 : False : False : Binary
(1, 4) : 0 : None : 1 : False : True : Binary
(1, 5) : 0 : 0.0 : 1 : False : False : Binary
(1, 6) : 0 : None : 1 : False : True : Binary
(1, 7) : 0 : None : 1 : False : True : Binary
(1, 8) : 0 : 0.0 : 1 : False : False : Binary
(1, 9) : 0 : 0.0 : 1 : False : False : Binary
(1, 10) : 0 : 0.0 : 1 : False : False : Binary
(2, 0) : 0 : None : 1 : False : True : Binary
(2, 1) : 0 : None : 1 : False : True : Binary
(2, 2) : 0 : None : 1 : False : True : Binary
(2, 3) : 0 : None : 1 : False : True : Binary
(2, 4) : 0 : 0.0 : 1 : False : False : Binary
(2, 5) : 0 : None : 1 : False : True : Binary
(2, 6) : 0 : 0.0 : 1 : False : False : Binary
(2, 7) : 0 : 0.0 : 1 : False : False : Binary
(2, 8) : 0 : 0.0 : 1 : False : False : Binary
(2, 9) : 0 : 0.0 : 1 : False : False : Binary
(2, 10) : 0 : 0.0 : 1 : False : False : Binary
(3, 0) : 0 : 0.0 : 1 : False : False : Binary
(3, 1) : 0 : None : 1 : False : True : Binary
(3, 2) : 0 : None : 1 : False : True : Binary
(3, 3) : 0 : None : 1 : False : True : Binary
(3, 4) : 0 : None : 1 : False : True : Binary
(3, 5) : 0 : None : 1 : False : True : Binary
(3, 6) : 0 : None : 1 : False : True : Binary
(3, 7) : 0 : None : 1 : False : True : Binary
(3, 8) : 0 : None : 1 : False : True : Binary
(3, 9) : 0 : None : 1 : False : True : Binary
(3, 10) : 0 : None : 1 : False : True : Binary
(4, 0) : 0 : 0.0 : 1 : False : False : Binary
(4, 1) : 0 : None : 1 : False : True : Binary
(4, 2) : 0 : None : 1 : False : True : Binary
(4, 3) : 0 : 0.0 : 1 : False : False : Binary
(4, 4) : 0 : None : 1 : False : True : Binary
(4, 5) : 0 : None : 1 : False : True : Binary
(4, 6) : 0 : None : 1 : False : True : Binary
(4, 7) : 0 : None : 1 : False : True : Binary
(4, 8) : 0 : None : 1 : False : True : Binary
(4, 9) : 0 : None : 1 : False : True : Binary
(4, 10) : 0 : None : 1 : False : True : Binary
(5, 0) : 0 : 0.0 : 1 : False : False : Binary
(5, 1) : 0 : None : 1 : False : True : Binary
(5, 2) : 0 : None : 1 : False : True : Binary
(5, 3) : 0 : 0.0 : 1 : False : False : Binary
(5, 4) : 0 : 0.0 : 1 : False : False : Binary
(5, 5) : 0 : None : 1 : False : True : Binary
(5, 6) : 0 : None : 1 : False : True : Binary
(5, 7) : 0 : None : 1 : False : True : Binary
(5, 8) : 0 : None : 1 : False : True : Binary
(5, 9) : 0 : None : 1 : False : True : Binary
(5, 10) : 0 : None : 1 : False : True : Binary
(6, 0) : 0 : None : 1 : False : True : Binary
(6, 1) : 0 : 0.0 : 1 : False : False : Binary
(6, 2) : 0 : None : 1 : False : True : Binary
(6, 3) : 0 : 0.0 : 1 : False : False : Binary
(6, 4) : 0 : 0.0 : 1 : False : False : Binary
(6, 5) : 0 : 0.0 : 1 : False : False : Binary
(6, 6) : 0 : None : 1 : False : True : Binary
(6, 7) : 0 : 0.0 : 1 : False : False : Binary
(6, 8) : 0 : 0.0 : 1 : False : False : Binary
(6, 9) : 0 : 0.0 : 1 : False : False : Binary
(6, 10) : 0 : 0.0 : 1 : False : False : Binary
(7, 0) : 0 : 0.0 : 1 : False : False : Binary
(7, 1) : 0 : None : 1 : False : True : Binary
(7, 2) : 0 : None : 1 : False : True : Binary
(7, 3) : 0 : 0.0 : 1 : False : False : Binary
(7, 4) : 0 : 0.0 : 1 : False : False : Binary
(7, 5) : 0 : 0.0 : 1 : False : False : Binary
(7, 6) : 0 : None : 1 : False : True : Binary
(7, 7) : 0 : None : 1 : False : True : Binary
(7, 8) : 0 : None : 1 : False : True : Binary
(7, 9) : 0 : None : 1 : False : True : Binary
(7, 10) : 0 : None : 1 : False : True : Binary
(8, 0) : 0 : 0.0 : 1 : False : False : Binary
(8, 1) : 0 : None : 1 : False : True : Binary
(8, 2) : 0 : None : 1 : False : True : Binary
(8, 3) : 0 : 0.0 : 1 : False : False : Binary
(8, 4) : 0 : 0.0 : 1 : False : False : Binary
(8, 5) : 0 : 0.0 : 1 : False : False : Binary
(8, 6) : 0 : None : 1 : False : True : Binary
(8, 7) : 0 : 0.0 : 1 : False : False : Binary
(8, 8) : 0 : None : 1 : False : True : Binary
(8, 9) : 0 : None : 1 : False : True : Binary
(8, 10) : 0 : None : 1 : False : True : Binary
(9, 0) : 0 : 0.0 : 1 : False : False : Binary
(9, 1) : 0 : None : 1 : False : True : Binary
(9, 2) : 0 : None : 1 : False : True : Binary
(9, 3) : 0 : 0.0 : 1 : False : False : Binary
(9, 4) : 0 : 0.0 : 1 : False : False : Binary
(9, 5) : 0 : 0.0 : 1 : False : False : Binary
(9, 6) : 0 : None : 1 : False : True : Binary
(9, 7) : 0 : 0.0 : 1 : False : False : Binary
(9, 8) : 0 : 0.0 : 1 : False : False : Binary
(9, 9) : 0 : None : 1 : False : True : Binary
(9, 10) : 0 : None : 1 : False : True : Binary
(10, 0) : 0 : 0.0 : 1 : False : False : Binary
(10, 1) : 0 : None : 1 : False : True : Binary
(10, 2) : 0 : None : 1 : False : True : Binary
(10, 3) : 0 : 0.0 : 1 : False : False : Binary
(10, 4) : 0 : 0.0 : 1 : False : False : Binary
(10, 5) : 0 : 0.0 : 1 : False : False : Binary
(10, 6) : 0 : None : 1 : False : True : Binary
(10, 7) : 0 : 0.0 : 1 : False : False : Binary
(10, 8) : 0 : 0.0 : 1 : False : False : Binary
(10, 9) : 0 : 0.0 : 1 : False : False : Binary
(10, 10) : 0 : None : 1 : False : True : Binary
Objectives:
objective : Size=1, Index=None, Active=True
Key : Active : Value
None : True : 5.0
Constraints:
c1 : Size=47
Key : Lower : Body : Upper
1 : None : -1.0 : 0.0
2 : None : -1.0 : 0.0
3 : None : -1.0 : 0.0
4 : None : -1.0 : 0.0
5 : None : -1.0 : 0.0
6 : None : -1.0 : 0.0
7 : None : -1.0 : 0.0
8 : None : -1.0 : 0.0
9 : None : -1.0 : 0.0
10 : None : -1.0 : 0.0
11 : None : -1.0 : 0.0
12 : None : -1.0 : 0.0
13 : None : -1.0 : 0.0
14 : None : -1.0 : 0.0
15 : None : -1.0 : 0.0
16 : None : -1.0 : 0.0
17 : None : -1.0 : 0.0
18 : None : -1.0 : 0.0
19 : None : -1.0 : 0.0
20 : None : -1.0 : 0.0
21 : None : -1.0 : 0.0
22 : None : 0.0 : 0.0
23 : None : 0.0 : 0.0
24 : None : 0.0 : 0.0
25 : None : 0.0 : 0.0
26 : None : 0.0 : 0.0
27 : None : 0.0 : 0.0
28 : None : 0.0 : 0.0
29 : None : -1.0 : 0.0
30 : None : -1.0 : 0.0
31 : None : -1.0 : 0.0
32 : None : -1.0 : 0.0
33 : None : 0.0 : 0.0
34 : None : -1.0 : 0.0
35 : None : -1.0 : 0.0
36 : None : -1.0 : 0.0
37 : None : -1.0 : 0.0
38 : None : -1.0 : 0.0
39 : None : -1.0 : 0.0
40 : None : 0.0 : 0.0
41 : None : -1.0 : 0.0
42 : None : -1.0 : 0.0
43 : None : -1.0 : 0.0
44 : None : -1.0 : 0.0
45 : None : -1.0 : 0.0
46 : None : 0.0 : 0.0
47 : None : -1.0 : 0.0
c2 : Size=47
Key : Lower : Body : Upper
1 : None : 0.0 : 0.0
2 : None : 0.0 : 0.0
3 : None : 0.0 : 0.0
4 : None : 0.0 : 0.0
5 : None : 0.0 : 0.0
6 : None : 0.0 : 0.0
7 : None : 0.0 : 0.0
8 : None : 0.0 : 0.0
9 : None : 0.0 : 0.0
10 : None : 0.0 : 0.0
11 : None : 0.0 : 0.0
12 : None : 0.0 : 0.0
13 : None : 0.0 : 0.0
14 : None : 0.0 : 0.0
15 : None : 0.0 : 0.0
16 : None : 0.0 : 0.0
17 : None : 0.0 : 0.0
18 : None : 0.0 : 0.0
19 : None : 0.0 : 0.0
20 : None : 0.0 : 0.0
21 : None : 0.0 : 0.0
22 : None : -1.0 : 0.0
23 : None : -1.0 : 0.0
24 : None : -1.0 : 0.0
25 : None : -1.0 : 0.0
26 : None : -1.0 : 0.0
27 : None : -1.0 : 0.0
28 : None : -1.0 : 0.0
29 : None : 0.0 : 0.0
30 : None : 0.0 : 0.0
31 : None : 0.0 : 0.0
32 : None : 0.0 : 0.0
33 : None : 0.0 : 0.0
34 : None : 0.0 : 0.0
35 : None : 0.0 : 0.0
36 : None : 0.0 : 0.0
37 : None : 0.0 : 0.0
38 : None : 0.0 : 0.0
39 : None : 0.0 : 0.0
40 : None : 0.0 : 0.0
41 : None : 0.0 : 0.0
42 : None : 0.0 : 0.0
43 : None : 0.0 : 0.0
44 : None : 0.0 : 0.0
45 : None : 0.0 : 0.0
46 : None : 0.0 : 0.0
47 : None : 0.0 : 0.0
c3 : Size=47
Key : Lower : Body : Upper
1 : None : 0.0 : 0.0
2 : None : 0.0 : 0.0
3 : None : 0.0 : 0.0
4 : None : 0.0 : 0.0
5 : None : 0.0 : 0.0
6 : None : 0.0 : 0.0
7 : None : 0.0 : 0.0
8 : None : 0.0 : 0.0
9 : None : 0.0 : 0.0
10 : None : 0.0 : 0.0
11 : None : 0.0 : 0.0
12 : None : 0.0 : 0.0
13 : None : 0.0 : 0.0
14 : None : 0.0 : 0.0
15 : None : 0.0 : 0.0
16 : None : 0.0 : 0.0
17 : None : 0.0 : 0.0
18 : None : 0.0 : 0.0
19 : None : 0.0 : 0.0
20 : None : 0.0 : 0.0
21 : None : 0.0 : 0.0
22 : None : 0.0 : 0.0
23 : None : 0.0 : 0.0
24 : None : 0.0 : 0.0
25 : None : 0.0 : 0.0
26 : None : 0.0 : 0.0
27 : None : 0.0 : 0.0
28 : None : 0.0 : 0.0
29 : None : 0.0 : 0.0
30 : None : 0.0 : 0.0
31 : None : 0.0 : 0.0
32 : None : 0.0 : 0.0
33 : None : -1.0 : 0.0
34 : None : 0.0 : 0.0
35 : None : 0.0 : 0.0
36 : None : 0.0 : 0.0
37 : None : 0.0 : 0.0
38 : None : 0.0 : 0.0
39 : None : 0.0 : 0.0
40 : None : -1.0 : 0.0
41 : None : 0.0 : 0.0
42 : None : 0.0 : 0.0
43 : None : 0.0 : 0.0
44 : None : 0.0 : 0.0
45 : None : 0.0 : 0.0
46 : None : -1.0 : 0.0
47 : None : 0.0 : 0.0
We observe that the optimal solution of this problem is \(x_{10} = 1, 0\) otherwise, leading to an objective of \(5\). Notice that this problem has a degenerate optimal solution given that \(x_8 = 1, 0\) otherwise also leads to the same solution.
We can also solve this problem using Simulated Annealing
simAnnSampler = neal.SimulatedAnnealingSampler()
simAnnSamples = simAnnSampler.sample(model_ising, num_reads=1000)
plot_enumerate(simAnnSamples, title='Simulated annealing in default parameters')
plot_energies(simAnnSamples, title='Simulated annealing in default parameters')
minimum energy: 5.0
minimum energy: 5.0
simAnnSamples.info
{'beta_range': [0.00041111932417553103, 0.1458971970580513],
'beta_schedule_type': 'geometric',
'timing': {'preprocessing_ns': 1475168,
'sampling_ns': 281521474,
'postprocessing_ns': 264931}}
Let’s solve the graph coloring problem using QUBO.#
Vertex \(k\)-coloring of graphs#
Given a graph \(G(V, E)\), where \(V\) is the set of vertices and \(E\) is the set of edges of \(G\), and a positive integer \(k\), we ask if it is possible to assign a color to every vertex from \(V\), such that adjacent vertices have different colors assigned.
\(G(V, E)\) has \(12\) vertices and \(23\) edges. We ask if the graph is \(3\)–colorable. Let’s first encode \(V\) and \(E\) using Julia’s built–in data structures:
Note: This tutorial is heavily inspired in D-Wave’s Map coloring of Canada found here.
# Let's install with dimod and neal
if IN_COLAB:
!pip install dwavebinarycsp
!pip install dwavebinarycsp[maxgap]
!pip install dwavebinarycsp[mip]
import dwavebinarycsp
V = range(1, 12+1)
E = [(1,2),(2,3),(1,4),(1,6),(1,12),(2,5),(2,7),(3,8),(3,10),(4,11),(4,9),(5,6),(6,7),(7,8),(8,9),(9,10),(10,11),(11,12),(5,12),(5,9),(6,10),(7,11),(8,12)]
layout = {i: [np.cos((2*i+1)*np.pi/8),np.sin((2*i+1)*np.pi/8)] for i in np.arange(5,13)}
layout[1] = [-1.5,1.5]
layout[2] = [1.5,1.5]
layout[3] = [1.5,-1.5]
layout[4] = [-1.5,-1.5]
G = nx.Graph()
G.add_edges_from(E)
nx.draw(G, with_labels=True, pos=layout)
# Function for the constraint that two nodes with a shared edge not both select
# one color
def not_both_1(v, u):
return not (v and u)
# Valid configurations for the constraint that each node select a single color, in this case we want to use 3 colors
one_color_configurations = {(0, 0, 1), (0, 1, 0), (1, 0, 0)}
colors = len(one_color_configurations)
# Create a binary constraint satisfaction problem
csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY)
# Add constraint that each node select a single color
for node in V:
variables = ['x'+str(node)+','+str(i) for i in range(colors)]
csp.add_constraint(one_color_configurations, variables)
# Add constraint that each pair of nodes with a shared edge not both select one color
for edge in E:
v, u = edge
for i in range(colors):
variables = ['x'+str(v)+','+str(i), 'x'+str(u)+','+str(i)]
csp.add_constraint(not_both_1, variables)
Defining the Binary Quandratic model (QUBO) using the CSP library we have:
bqm = dwavebinarycsp.stitch(csp)
simAnnSamples = simAnnSampler.sample(bqm, num_reads=1000)
plot_enumerate(simAnnSamples, title='Simulated annealing in default parameters')
plot_energies(simAnnSamples, title='Simulated annealing in default parameters')
minimum energy: 0.0
minimum energy: 0.0
Because of precision issues in the translation to BQM, we may obtain very tiny coefficeints that should be zero. In any case, since this is a constraint satisfaction problem, any of the solutions with energy ~0 is a valid coloring.
# Check that a good solution was found
sample = simAnnSamples.first.sample # doctest: +SKIP
if not csp.check(sample): # doctest: +SKIP
print("Failed to color map. Try sampling again.")
else:
print(sample)
{'x1,0': 1, 'x1,1': 0, 'x1,2': 0, 'x10,0': 1, 'x10,1': 0, 'x10,2': 0, 'x11,0': 0, 'x11,1': 1, 'x11,2': 0, 'x12,0': 0, 'x12,1': 0, 'x12,2': 1, 'x2,0': 0, 'x2,1': 1, 'x2,2': 0, 'x3,0': 0, 'x3,1': 0, 'x3,2': 1, 'x4,0': 0, 'x4,1': 0, 'x4,2': 1, 'x5,0': 1, 'x5,1': 0, 'x5,2': 0, 'x6,0': 0, 'x6,1': 1, 'x6,2': 0, 'x7,0': 0, 'x7,1': 0, 'x7,2': 1, 'x8,0': 1, 'x8,1': 0, 'x8,2': 0, 'x9,0': 0, 'x9,1': 1, 'x9,2': 0}
# Function that plots a returned sample
def plot_map(sample):
# Translate from binary to integer color representation
color_map = {}
for node in V:
for i in range(colors):
if sample['x'+str(node)+','+str(i)]:
color_map[node] = i
# Plot the sample with color-coded nodes
node_colors = [color_map.get(node) for node in G.nodes()]
nx.draw(G, with_labels=True, pos=layout, node_color=node_colors)
plt.show()
plot_map(sample)
